class Solution(object):
    def numDistinct(self, s, t):
        dp = [[0 for _ in range(len(s)+1)] for _ in range(len(t)+1)]
        for i in range(len(s)+1):
            dp[0][i]=1
        
        for ti in range(len(t)):
            for si in range(len(s)):
                if s[si]==t[ti]:
                    dp[ti+1][si+1] = dp[ti][si]+dp[ti+1][si]
                else:
                    dp[ti+1][si+1] = dp[ti+1][si]
        return dp[-1][-1]

print(Solution().numDistinct("abab", "ab"))